import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }
    public void dfs(List<Integer> a,List<Integer> b,List<Integer> c,int n){
        if(n==1){
            c.add(a.remove(a.size()-1));
            return;
        }
        dfs(a,c,b,n-1);
        c.add(a.remove(a.size()-1));
        dfs(b,a,c,n-1);
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }
        else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode newHead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode tmp=swapPairs(head.next.next);
        head.next.next=head;
        ListNode newHead=head.next;
        head.next=tmp;
        return newHead;
    }
    public double myPow(double x, int n) {
        return n>0?Pow(x,n):1.0/Pow(x,-n);
    }
    public double Pow(double x,int n){
        if(n==0) return 1.0;
        double ret=Pow(x,n/2);
        return n%2==0?ret*ret:ret*ret*x;
    }
    public boolean evaluateTree(TreeNode root) {
        if(root.left==null) return root.val==0?false:true;
        boolean left=evaluateTree(root.left);
        boolean right=evaluateTree(root.right);
        return root.val==2?left||right:left&&right;
    }
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    public int dfs(TreeNode root,int preSum){
        if(root==null) return 0;
        int ret=preSum*10+root.val;
        if(root.left==null&&root.right==null) return ret;
        else return dfs(root.left,ret)+dfs(root.right,ret);
    }
    public TreeNode pruneTree(TreeNode root) {
        if(root==null) return null;
        root.left=pruneTree(root.left);
        root.right=pruneTree(root.right);
        if(root.left==null&&root.right==null&&root.val==0) return null;
        return root;
    }
    long pre=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean left = isValidBST(root.left);
        boolean cur=false;
        if(root.val>pre) cur=true;
        pre=root.val;
        boolean right=isValidBST(root.right);
        return left&&cur&&right;
    }
    List<String> ret;
    public List<String> binaryTreePaths(TreeNode root) {
        ret=new ArrayList<>();
        dsp(root,"");
        return ret;
    }
    public void dsp(TreeNode root,String prePath){
        StringBuffer path=new StringBuffer(prePath);
        path.append(Integer.toString(root.val));
        if(root.left==null&&root.right==null){
            ret.add(path.toString());
            return;
        }
        path.append("->");
        if(root.left!=null) dsp(root.left,path.toString());
        if(root.right!=null) dsp(root.right,path.toString());
    }
    boolean[] check;
    List<Integer> path;
    List<List<Integer>> ret2;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        check=new boolean[nums.length];
        path=new ArrayList<>();
        ret=new ArrayList<>();
        dfs(nums,0);
        return ret2;
    }
    public void dfs(int[] nums,int pos){
        if(pos==nums.length){
            ret2.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==true)){
                continue;
            }
            path.add(nums[i]);
            check[i]=true;
            dfs(nums,pos+1);
            path.remove(path.size()-1);
            check[i]=false;
        }
    }
    boolean[] ch;
    List<Integer> path1;
    List<List<Integer>> ret3;
    public List<List<Integer>> permute(int[] nums) {
        ch=new boolean[nums.length];
        path1=new ArrayList<>();
        ret3=new ArrayList<>();
        dfs1(nums,0);
        return ret3;
    }
    public void dfs1(int[] nums,int pos){
        if(pos==nums.length){
            ret3.add(new ArrayList<>(path1));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(ch[i]==true) continue;
            path1.add(nums[i]);
            ch[i]=true;
            dfs1(nums,pos+1);
            path1.remove(path1.size()-1);
            ch[i]=false;
        }
    }
    int sum;
    public int subsetXORSum(int[] nums) {
        dfs(nums,0,0);
        return sum;
    }
    public void dfs(int[] nums,int pos,int path){
        if(pos==nums.length){
            sum+=path;
            return;
        }
        dfs(nums,pos+1,path^nums[pos]);
        dfs(nums,pos+1,path);
    }
    public List<String> letterCombinations(String digits) {
        List<String> list=new ArrayList<String>();
        if(digits.length()==0){
            return list;
        }
        Map<Character, String> hashmap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(list,hashmap,digits,0,new StringBuffer());
        return list;
    }
    public void backtrack(List<String> list,Map<Character,String> hashmap,String digits,int indx,StringBuffer sb){
        if(indx==digits.length()){
            list.add(sb.toString());
        }
        else{
            char dig=digits.charAt(indx);
            String letters=hashmap.get(dig);
            for(int i=0;i<letters.length();i++){
                sb.append(letters.charAt(i));
                backtrack(list,hashmap,digits,indx+1,sb);
                sb.deleteCharAt(indx);
            }
        }
    }
    int n;
    StringBuffer path2;
    List<String> ret4;
    public List<String> generateParenthesis(int _n) {
        ret4=new ArrayList<>();
        path2=new StringBuffer();
        n=_n;
        dfs(0,0);
        return ret4;
    }
    public void dfs(int left,int right){
        if(right==n){
            ret.add(path2.toString());
            return;
        }
        if(left<n){
            path2.append('(');
            dfs(++left,right);
            path2.deleteCharAt(path2.length()-1);
            left--;
        }
        if(right<left){
            path2.append(')');
            dfs(left,++right);
            path2.deleteCharAt(path2.length()-1);
            right--;
        }
    }

    int x,m;
    public List<List<Integer>> combine(int n, int k) {
        path=new ArrayList<>();
        ret=new ArrayList<>();
        x=k;m=n;
        dfs(1);
        return ret3;
    }
    public void dfs(int pos){
        if(x==path.size()){
            ret3.add(new ArrayList<>(path1));
            return;
        }
        for(int i=pos;i<=m;i++){
            path1.add(i);
            dfs(i+1);
            path1.remove(path.size()-1);
        }
    }
    int n6;
    int ret6;
    public int findTargetSumWays(int[] nums, int target) {
        n6=target;
        ret6=0;
        dfs(nums,0,0);
        return ret6;
    }
    public void dfs4(int[] nums,int sum,int pos){
        if(pos==nums.length){
            if(sum==n) ret6++;
            return;
        }
        dfs4(nums,sum+nums[pos],pos+1);
        dfs4(nums,sum-nums[pos],pos+1);
    }
    List<String> ret7;
    StringBuffer path6;
    public List<String> letterCasePermutation(String s) {
        ret7=new ArrayList<>();
        path6=new StringBuffer();
        dfs(s,0);
        return ret7;
    }
    public void dfs(String s,int pos){
        if(pos==s.length()){
            ret.add(path.toString());
            return;
        }
        char ch=s.charAt(pos);
        path6.append(ch);
        dfs(s,pos+1);
        path6.deleteCharAt(path6.length()-1);
        if(s.charAt(pos)>'9'||s.charAt(pos)<'0'){
            ch=change(s.charAt(pos));
            path6.append(ch);
            dfs(s,pos+1);
            path6.deleteCharAt(path6.length()-1);
        }
    }
    public char change(char s){
        if(s>='a'&&s<='z') s-=32;
        else s+=32;
        return s;
    }
}